package 分类.双指针;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 三数之和 {

    public List<List<Integer>> threeSum(int[] nums) {
         Arrays.sort(nums);

         return three(nums,3,0,0);

    }
    List<List<Integer>> three(int[] nums,int n,int start,int sum){
        List<List<Integer>> res=new LinkedList<>();
        if(n<2||n>nums.length) return res;
        if(n==2){
           int lo=start;
           int hi=nums.length-1;
           while (lo<hi){
               int sum0=nums[lo]+nums[hi];
               int left=nums[lo];
               int right=nums[hi];
               if(sum0<sum){
                   while (lo<hi&&nums[lo]==left) lo++;
               }else if(sum0>sum){
                   while (lo<hi&&nums[hi]==right) hi--;
               }else {
                   List<Integer> list=new LinkedList<>();
                   list.add(left);
                   list.add(right);
                   res.add(list);
                   while (lo<hi&&nums[lo]==left) lo++;
                   while (lo<hi&&nums[hi]==right) hi--;
               }
           }
        }else {
            for (int i=0;i<nums.length;i++){
                List<List<Integer>> res1=three(nums,n-1,i+1,sum-nums[i]);
                for (List<Integer> list : res1) {
                    list.add(nums[i]);
                    res.add(list);
                }
                while(i<nums.length-1&&nums[i]==nums[i+1]) i++;
            }
        }
        return res;
    }
}
